Educational Codeforces Round #135

A

求出最大值所在下标即可。时间复杂度 $O(n)$ 。

Code

#include <cstdio>

int T, n, x, v, pos;

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        pos = v = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &x);
            if (x > v) v = x, pos = i;
        }
        printf("%d\n", pos);
    }
}

B

容易发现最大值为 $2n-1$ ，所以只需要把 $n-1$ 和 $n$ 放在最后两位即可。

若 $n$ 为奇数则按照 $1,\,n-2,\,n-3,\,\cdots,\,2,\,n-1,\,n$ 排列。

若 $n$ 为偶数则按照 $n-2,\,n-3,\,\cdots,\,2,\,1,\,n-1,\,n$ 排列。

容易说明这是一种最优的排列方式。

Code

#include <cstdio>

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        if (n % 2) {
            printf("1 ");
            for (int i = n - 2; i >= 2; i--) printf("%d ", i);
            printf("%d %d\n", n - 1, n);
        } else {
            for (int i = n - 2; i >= 1; i--) printf("%d ", i);
            printf("%d %d\n", n - 1, n);
        }
    }
}

C

开两个 $\text{map}$ 记录一位数和两位数及以上的数的出现次数，直接计数即可。

时间复杂度 $O(n\log{n})$ 。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;

const int N = 2e5 + 5;

int a[N], b[N], n, ans, T;
map<int, int> s, t;

inline int count(int x) {
    int ret = 0;
    while (x) ret++, x /= 10;
    return ret;
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        ans = 0;
        s.clear(), t.clear();
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            if (a[i] >= 10) s[a[i]]++;
            else t[a[i]]++;
        }
        for (int i = 1; i <= n; i++) {
            scanf("%d", &b[i]);
            if (b[i] >= 10) s[b[i]]--;
            else t[b[i]]--;
        }
        for (auto it: s) {
            int j = it.first, k = it.second;
            if (k > 0) t[count(j)] += k, ans += k;
            if (k < 0) t[count(j)] += k, ans -= k;
        }
        for (auto it: t) {
            int j = it.first, k = it.second;
            if (k > 0 && j != 1) ans += k;
            if (k < 0 && j != 1) ans -= k;
        }
        printf("%d\n", ans);
    }
}

D

注意到Bob永远都赢不了，那他为什么要玩这个游戏。

对于当前的一个串 $S$ ，我们分情况讨论：

若 $|S|=2$ ，则只有在两个字符相同时平局。

若 $|S|\ge 4$ ，考虑从只有两个字符的状态添加字符转移。容易发现只有当Bob能跟Alice拿一样的字符时是平局，否则在每一轮中Alice都可以取到比Bob不劣的字符，最后一定是Alice获胜。

所以我们一直判断是否有头尾相同/头上连续两个相同/尾上连续两个相同，并调整头尾指针即可。

再注意到头尾相同的优先级要高于头尾连续相同。时间复杂度 $O(n)$ 。

Code

#include <cstdio>
#include <cstring>

const int N = 2005;

char s[N];

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%s", s + 1);
        int l = 1, r = strlen(s + 1);

        while (l <= r && s[l] == s[r]) l++, r--;

        if (l > r) {
            puts("Draw");
            continue;
        }

        while (l <= r) {
            if (s[l] == s[l + 1]) l += 2;
            if (s[r] == s[r - 1]) r -= 2;
            else break;
        }

        puts(l <= r ? "Alice" : "Draw");
    }
}

E

待补。

F

待补。

G

待补。